#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define endl '\n'
const int N = 25;
const int INF = 1e9;
int n, m;
int g[N][N];
int deg[N];
int dp[1 << 15];

void floyd() {
  rep(k, 1, n) rep(i, 1, n) rep(j, 1, n) g[i][j] =
      min(g[i][j], g[i][k] + g[k][j]);
}
int dfs(int s) {
  if (s == 0) return 0;
  if (dp[s]) return dp[s];
  int res = INF;
  rep(i, 0, n - 1) {
    if (!(s & (1 << i))) continue;
    rep(j, i + 1, n - 1) {
      if (!(s & (1 << j))) continue;
      res = min(res, g[i + 1][j + 1] + dfs(s ^ (1 << i) ^ (1 << j)));
    }
  }
  return dp[s] = res;
}
void solve() {
  ll sum = 0;
  cin >> n >> m;
  rep(i, 1, n) rep(j, 1, n) g[i][j] = i == j ? 0 : INF;
  rep(i, 1, m) {
    int u, v, w;
    cin >> u >> v >> w;
    sum += w;
    g[u][v] = g[v][u] = min(g[u][v], w);
    deg[u]++, deg[v]++;  // also works for loop
  }
  floyd();
  rep(i, 1, n) {
    if (g[1][i] >= INF && deg[i]) {
      cout << -1;
      return;
    }
  }
  int mask = 0;
  rep(i, 1, n) if (deg[i] & 1) mask |= 1 << (i - 1);
  sum += dfs(mask);
  cout << sum;
  return;
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t = 1;
  while (t--) solve();
  return 0;
}